/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-17
 * Time: 10:31
 */
class Trie{
    public Trie[] child;
    public boolean isFinished; // 标记是否结束
    public Trie(){
        this.child = new Trie[26];
    }
}

public class MagicDictionary {
    public Trie root = new Trie();

    /** Initialize your data structure here. */
    public MagicDictionary() {

    }


    /**
     * 构造字典树
     * @param dictionary
     */
    public void buildDict(String[] dictionary) {
        for (String s: dictionary) {
            Trie cur = this.root;
            for (Character c: s.toCharArray()) {
                if (cur.child[c - 'a'] == null){
                    cur.child[c - 'a'] = new Trie();
                }
                cur = cur.child[c - 'a'];
            }
            cur.isFinished = true;
        }
    }

    public boolean search(String searchWord) {
        return searchWord(this.root, searchWord, 0, false);
    }

    public boolean searchWord(Trie cur, String searchWord, int pos, boolean modified){
        // 匹配完了
        if (pos == searchWord.length()){
            // 匹配完了同时需要注意是不是某个单词的结尾
            return modified && cur.isFinished;
        }
        // 还没匹配完
        Trie next = cur.child[searchWord.charAt(pos) - 'a'];
        if (next != null){
            // 匹配上了
            if (searchWord(next, searchWord, pos + 1, modified)){
                return true;
            }
        }
        // 没有匹配上
        // 那就把这个字母当作要修改的哪个字母
        if (!modified){
            // 还没有修改过
            char c = searchWord.charAt(pos);
            for (int i = 0; i < 26; i++) {
                // 不是同一个字母才能设置为已经修改
                if (cur.child[i] != null && i != (c - 'a')){
                    if (searchWord(cur.child[i], searchWord, pos + 1, true)){
                        return true;
                    }
                }
            }
        }
        return false;
    }
}
